#include"Heap.h"

void HeapInint(Heap* hp)
{
	assert(hp);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
	
}

void CheackCapacity(Heap* hp)
{
	assert(hp);
	//满了就扩容
	if (hp->_capacity == hp->_size)
	{
		int newcapacity = hp->_capacity==0?4:hp->_capacity*2;
		HPDataType*tmp=(HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail\n");
			return;
		}
		hp->_capacity = newcapacity;
		hp->_a = tmp;
	}
}


void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->_a);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}

void Sweap(HPDataType* n1, HPDataType* n2)
{
	HPDataType tmp = *n1;
	*n1 = *n2;
	*n2 = tmp;
}

//建大堆
void AdjustUp(HPDataType*a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[parent] < a[child])
		{
			Sweap(&a[parent], &a[child]);
			child = parent;
		}
		else
		{
			break;
		}
		parent = (child - 1) / 2;
	}
}

void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	CheackCapacity(hp);

	hp->_a[hp->_size] = x;
	hp->_size++;
	
	AdjustUp(hp->_a, hp->_size-1);

}

void AdjustDown(HPDataType* a, int parent, int n)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child<n)
	{
		//找左 右孩子大的一个
		if (child+1<n &&a[child] < a[child + 1])
		{
			child++;
		}
		if (a[parent] < a[child])
		{
			Sweap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
		
	}
}

bool HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->_size == 0;
}

void HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

	Sweap(&hp->_a[0], &hp->_a[hp->_size - 1]);

	AdjustDown(hp->_a, 0,hp->_size-1);

	hp->_size--;

}

int HeapSize(Heap* hp)
{
	assert(hp);

	return hp->_size;
}

HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

	return hp->_a[0];
}

void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
	assert(a);

	hp->_capacity = n;
	hp->_size = n;

	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, i, n);
	}
	hp->_a = a;

}